#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>void read(T &x){char CH=getch();int fl=1;x=0;while(CH>'9'||CH<'0'){if(CH=='-')fl=-1;CH=getch();}while(CH<='9'&&CH>='0'){x=x*10+CH-48;CH=getch();}x*=fl;}
	template<typename T>void read_s(T &x){x="";char CH=getch();while(!(CH>='a'&&CH<='z')&&!(CH>='A'&&CH<='Z'))CH=getch();while((CH>='a'&&CH<='z')||(CH>='A'&&CH<='Z')){x+=CH;CH=getch();}}
	template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char CH) {if(p3-obuf<(1<<21))*p3++=CH;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=CH;}
	char CH[100];
	template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)CH[++top]=x%10+48,x/=10;while(top)putch(CH[top]),top--;}
	template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);putch(' ');write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,m;
int a[100005];
vector<int>p[100005];
struct node{int l,r,v;};
vector<node>q[5][100005];
struct Shiki
{
	struct segt
	{
		int val,tag;
	}t[100005<<2];
	#define mid (l+r>>1)
	#define ls (root<<1)
	#define rs (root<<1|1)
	void add(int x,int y,int v,int root=1,int l=1,int r=n)
	{
		if(l>=x&&r<=y)
		{
			t[root].tag+=v;
			if(t[root].tag) t[root].val=r-l+1;
			else if(l==r) t[root].val=0;
			else t[root].val=t[ls].val+t[rs].val;
			return;
		}
		if(x<=mid) add(x,y,v,ls,l,mid);
		if(y>mid) add(x,y,v,rs,mid+1,r);
		if(t[root].tag) t[root].val=r-l+1;
		else t[root].val=t[ls].val+t[rs].val;
	}
}T[1<<4];
signed main()
{
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	read(n,m);
	for(int i=1;i<=n;i++) p[i].push_back(0);
	for(int i=1;i<=n;i++) read(a[i]),p[a[i]].push_back(i);
	for(int i=1;i<=n;i++) p[i].push_back(n+1);
	for(int i=1;i<=n;i++)
		for(int len=1;len<=m;len++)
			for(int j=1;j+len-1<p[i].size()-1;j++)
			{
				q[len][p[i][j-1]+1].push_back((node){p[i][j+len-1],p[i][j+len]-1,1});
				q[len][p[i][j]+1].push_back((node){p[i][j+len-1],p[i][j+len]-1,-1});
			}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int s=1;s<(1<<m);s++)
			for(int k=1;k<=m;k++)
				if(s&(1<<k-1)) for(node j:q[k][i]) T[s].add(j.l,j.r,j.v);
		for(int s=1;s<(1<<m);s++) ans+=(__builtin_popcount(s)&1?1:-1)*T[s].t[1].val;
	}
	write(ans);
	flush();
	return 0;
}

